package com.gxc.string;

import java.util.HashMap;
import java.util.Map;

/**
 * 在一个字符串中找到没有重复字符子串中最长的长度。
 * 例如:
 * abcabcbb 没有重复字符的最长子串是abc，长度为3
 * bbbbb，答案是b，长度为1
 * pwwkew，答案是wke，长度是3
 * 要求:答案必须是子串，”pwke”是一个子字符序列但不是一个子字符串。
 *
 * 解法：
 * map<Character, integer> 记录每个字符最新出现的位置
 * start 当前字符的头位置
 * max  没有重复字符子串中最长的长度
 */
public class MaximumNonRepetition {

    public static void main(String[] args) {
        int size = 1000;
        for (int i = 0; i < size; i++) {
            String arr = random();
            if (longest(arr)!=longest2(arr)) {
                System.out.println(arr);
                System.out.println("算法错误");
                break;
            }
        }

        //System.out.println(randomC());


        String str = "vpwkpchyvr";
        System.out.println(longest(str));
        System.out.println(longest2(str));

        /*str = "bbbbb";
        System.out.println(longest(str));
        System.out.println(longest2(str));

        str = "pwwkew";
        System.out.println(longest(str));
        System.out.println(longest2(str));

        str = "abcd";
        System.out.println(longest(str));
        System.out.println(longest2(str));*/
    }

    public static int longest(String str) {
        if (str == null || str == "") return 0;

        int max = 0;
        int cur = 0;
        int pre = -1;
        Map<Character, java.lang.Integer> map = new HashMap<>();
        char[] chars = str.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            //当前字符最近出现的位置和上一个重复字符的位置比较
            if (map.containsKey(chars[i])) pre = Math.max(pre, map.get(chars[i]));
            cur = i - pre ;
            max = Math.max(cur, max);
            map.put(chars[i], i);
        }
        return max;
    }

    public static int longest2(String str) {
        if (str == null || str == "") return 0;

        int max = 0;
        int pre = -1;
        int cur = 0;
        char[] chars = str.toCharArray();

        //代替map
        int[] map = new int[255];
        for (int i = 0; i < map.length; i++) {
            map[i] = -1;
        }
        for (int i = 0; i < chars.length; i++) {
            pre = Math.max(pre, map[chars[i]]);
            cur = i - pre;
            max = Math.max(cur, max);
            map[chars[i]] = i;
        }
        return max;
    }

    private static String random() {
        int length = (int) (10* Math.random() + 1);
        StringBuffer buffer = new StringBuffer();
        for (int i = 0; i < length; i++) {
            buffer.append(randomC());
        }
        return buffer.toString();
    }

    private static Character randomC() {
        char length = (char) ((Math.random() * 27)+97);
        return length;
    }

}
